package g
/*
 * @lc app=leetcode.cn id=67 lang=golang
 *
 * [67] 二进制求和
 */

// @lc code=start
func addBinary(a string, b string) string {
	if len(a) < len(b) { // assert len(a) >= len(b)
		c := b
		b = a
		a = c
	}
	result := make([]byte, len(a)+1)
	for i := 0; i < len(result); i++ {
		result[i] = '0'
	}

	var carryBit byte
	delta := len(a) - len(b)
	for i := len(b) - 1; i >= 0; i-- {
		newBit := carryBit + a[i+delta] - '0' + b[i] - '0'
		if newBit >= 2 {
			carryBit = 1
			result[i+delta+1] += newBit - 2
		} else {
			carryBit = 0
			result[i+delta+1] += newBit
		}
	}
	for i := delta - 1; i >= 0; i-- {
		newBit := carryBit + a[i] - '0'
		if newBit >= 2 {
			carryBit = 1
			result[i+1] += newBit - 2
		} else {
			carryBit = 0
			result[i+1] += newBit
		}
	}
	if carryBit == 1 {
		result[0]++
	} else {
		result = result[1:]
	}
	return string(result)
}


// @lc code=end

